package com.cuz.for2024;

import java.math.BigInteger;
import java.util.Arrays;

public class T940 {

    public static void main(String[] args) {
        System.out.println(new T940().distinctSubseqII("aba"));
        System.out.println(new T940().distinctSubseqII2("aba"));
        System.out.println(new T940().distinctSubseqII("zchmliaqdgvwncfatcfivphddpzjkgyygueikthqzyeeiebczqbqhdytkoawkehkbizdmcnilcjjlpoeoqqoqpswtqdpvszfaksn"));
    }

    private static int mod = (int) (1e9 + 7);

    public int distinctSubseqII2(String s) {
        int[][] dp = new int[s.length()][26];
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            char cur = s.charAt(i);
            for (int j = 0; j < 26; j++) {
                if (cur == 'a' + j) {
                    int ans = 1;
                    for (int k = 0; k < 26 && i > 0; k++) {
                        ans = (ans + dp[i - 1][k]) % mod;
                    }
                    dp[i][j] = ans;
                } else {
                    dp[i][j] = i > 0 ? dp[i - 1][j] : 0;
                }
                res = (res+dp[i][j])%mod;
            }
        }

        return res;
    }

    public int distinctSubseqII(String s) {
        int ans = 0;
        int[][] dp = new int[s.length()][26];
        for (int[] ints : dp) {
            Arrays.fill(ints, -1);
        }
        for (int i = 0; i < 26; i++) {
            char c = (char) ('a' + i);
            ans = (ans + process(s, s.length() - 1, c, dp)) % mod;
        }
        return ans;
    }

    private int process(String s, int i, char c, int[][] dp) {
        if (i < 0) {
            return 0;
        }
        if (i == 0) {
            return s.charAt(i) == c ? 1 : 0;
        }
        if (dp[i][c - 'a'] != -1) {
            return dp[i][c - 'a'];
        }
        if (s.charAt(i) == c) {
            int ans = 1;
            for (int j = 0; j < 26; j++) {
                ans = (ans + process(s, i - 1, (char) ('a' + j), dp)) % mod;
            }
            dp[i][c - 'a'] = ans;
            return ans;
        } else {
            int ans = process(s, i - 1, c, dp) % mod;
            dp[i][c - 'a'] = ans;
            return ans;
        }
    }
}
